\documentclass[titlepage,12pt,a4paper]{article}
\usepackage{latexsym}
\usepackage[utf8]{inputenx}
\usepackage[spanish]{babel}
\usepackage{graphicx}
\usepackage{anysize}
\usepackage{amsmath}
\usepackage{float}
\usepackage{listings}
\usepackage{verbatim}
\usepackage{color}
\setcounter{tocdepth}{5}
\lstset {breaklines=true,
		 basicstyle=\scriptsize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Portada
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Margenes

\marginsize{2cm}{2cm}{1cm}{4cm} 

% En la instrucción \title{..}, se escribe el título del documento.
\title{
  \textbf{75.06 Organización de Datos} \\
  \vspace{0.5cm}
  Trabajo Práctico: Buscador usando LSI \\
  \vspace{1cm}
Entrega de Diseño \\
\vspace{2cm}
Cátedra: Argerich\\
\vspace{1cm}
  \emph{2do cuatrimestre 2012} \\
  \vspace{2cm}
  \begin{table}[h]
  \centering
  \begin{tabular}{|@{ \hspace{1cm} } c @{ \hspace{1cm} }| @{ \hspace{1cm} } c @{ \hspace{1cm} }| @{ \hspace{0.5cm} } c @{ \hspace{0.5cm} } |}
  \hline
  \textbf{Apellido y Nombre} & \textbf{E-mail} & \textbf{Padrón} \\
  \hline
	Montoya, Diego Ramiro &diegormontoya@gmail.com &91939	\\
  \hline
	Quevedo, Federico  &federico1245@gmail.com &93159	\\
  \hline
	Smulevici, Jorge &jorgsmu@gmail.com &93186	\\
  \hline
  \end{tabular}
  \end{table}
}

\author{  } % Aqui se pueden escribir los nombres de varios autores, separados por la instrucción \and.

% Aquí podemos escribir la fecha de realización del trabajo práctico. La fecha actual se escribe con \today. Si no se quiere incluir la fecha, dejar la instrucción en blanco.
\date{ \today }


	\begin{document}
		\maketitle
		\tableofcontents
		\newpage


\section {Introducción}



	El desarrollo práctico consiste en la realización de una búsqueda ranqueada sobre una cantidad de documentos, utilizando para ello el método conocido como LSI (Análisis Semántico Latente). 

	Dado un repositorio, la aplicación deberá indexar una cantidad variable de documentos de manera escalable. 
	Asimismo, deberá soportar búsquedas sobre los mismos devolviendo los resultado de manera eficiente, ranqueando por relevancia con el término que se desea encontrar.
	
	Se codificará en lenguaje C y se tomará como idioma para los textos el inglés, en caso de que este influya en el funcionamiento de algún algoritmo.
	
	\subsection{Latent semantic indexing}
		
	La Indexación Semántica Latente, conocida como LSI, es un método de indexación y recuperación de datos basado en la descomposición en valores singulares (SVD). Se diferencia de otros métodos en que la búsqueda no se realiza mediante el match de palabras, sino mediante la identificación de patrones entre los términos y conceptos contenidos en el espacio de documentos proporcionado.
  
	LSI se basa en el principio de que las palabras que se utilizan en los mismos contextos tienden a tener un significado similar. Esto es importante ya que ha se determinado que dos personas al hacer una misma búsqueda, se refieren al mismo concepto utilizando la misma palabra sólo en un 20\% de los casos. [\ref{FurnasLandauer}] 

	Es por este motivo que LSI presenta un comportamiento aceptable frente a dos grandes problemas lingüísticos que se dan en los sistemas de información, que son la \emph{sinonimia} y la \emph{polisemia}. La primera se refiere al hecho de que se puede hacer referencia a un mismo concepto utilizando distintas palabras, que son llamadas sinónimos[\ref{Sinonimia}]; la segunda se refiere a las palabras que se escriben de igual manera, pero según el contexto en que se usen tienen significados diferentes[\ref{Polisemia}].
	LSI presenta una solución a estos problemas gracias al manejo que hace sobre ``conceptos`` según el contexto en el que se encuentran, abstrayéndose de los términos específicos utilizados en los documentos.[\ref{Barbara_Rosario}]

	Al tener un conjunto de documentos a los cuales se quiere indexar y realizar consultas utilizando LSI, el primer paso consiste en el armado de una matriz M de \emph{n}x\emph{k}, donde n es el número total de términos existentes en el conjunto de documentos, y k es la cantidad de documentos. Ante esta disposición se puede decir que los documentos viven en el espacio columna de la matriz M, y los términos en el espacio fila.

	Cada posición M[i,j] de la matriz representa la intersección entre un término y un documento. El valor existente en una posición está determinado por el peso o importancia del término en el documento. El mismo puede ser la cantidad de repeticiones que se dieron, o el resultado de alguna función de ponderación de términos como se verá más adelante.

	Una vez armada la matriz M, se realiza la descomposición SVD de la misma, obteniendo 3 matrices, las cuales serán utilizadas para las consultas que se realizarán al modelo.

	Se procederá a explicar como se aplica este método, para luego hacer hincapié en las diferencias entre implementaciones y sus variaciones respecto a su eficacia. 
	
	\subsection{SVD}

	Se mostrará a continuación a modo de ejemplo un caso típico presentado en varios papers del tema [\ref{Scott_Deerwester}][\ref{FurnasLandauer}] , donde se generó la matriz M[i,j] y cada posición en dicha matriz representa la cantidad de repeticiones del término en dicho documento.

  \begin{itemize}
  \item{\textbf{c1}: Human machine interface for ABC computer applications}
  \item{\textbf{c2}: A survey of user opinion of computer system response time}
  \item{\textbf{c3}: The EPS user interface management system}
  \item{\textbf{c4}: System and human system engineering testing of EPS}
  \item{\textbf{c5}: Relation of user perceived response time to error measurement}

  \item{\textbf{m1}: The generation of random, binary, ordered trees}
  \item{\textbf{m2}: The intersection graph of paths in trees}
  \item{\textbf{m3}: Graph minors IV: Widths of trees and well-quasi-ordering}
  \item{\textbf{m4}: Graph minors: A survey}
  \end{itemize}

\[
\begin{matrix}
		& c1 & c2 & c3 & c4 & c5 & m1 & m2 & m3 & m4	\\
human	&  1  &  0  &  0 &  1  &  0  &  0   &  0  &  0   &  0		\\
interface	&  1  &  0  &  1 &  0  &  0  &  0   &  0  &  0   &  0		\\
computer	&  1  &  1  &  0 &  0  &  0  &  0   &  0  &  0   &  0		\\
user		&  0  &  1  &  1 &  0  &  1  &  0   &  0  &  0   &  0	 	\\
system	&  0  &  1  &  1 &  2  &  0  &  0   &  0  &  0   &  0	 	\\
response	&  0  &  1  &  0 &  0  &  1  &  0   &  0  &  0   &  0	 	\\
time		&  0  &  1  &  0 &  0  &  1  &  0   &  0  &  0   &  0	 	\\
EPS		&  0  &  0  &  1 &  1  &  0  &  0   &  0  &  0   &  0	 	\\
survey	&  0  &  1  &  0 &  0  &  0  &  0   &  0  &  0   &  1	 	\\
trees		&  0  &  0  &  0 &  0  &  0  &  1   &  1  &  1   &  0	 	\\
graph		&  0  &  0  &  0 &  0  &  0  &  0   &  1  &  1   &  1	 	\\
minors		&  0  &  0  &  0 &  0  &  0  &  0   &  0  &  1   &  1	 	\\
\end{matrix}
\] \newline


	A esta matriz se le hace una descomposición en valores singulares obteniendo tres matrices denominadas \textbf{U} (representando a los términos), \textbf{S} (matriz diagonal de autovalores) y \textbf{V} (representando a los documentos). Estas matrices luego son recortadas en base a un valor k a fin de que ocupen menor cantidad de memoria, y además, obteniendo una mejora en la eficacia de la búsqueda como se tratara más adelante.

\begin{figure} 
  \centering 
    \includegraphics[width=13cm]{Imagenes/SVD.png} 
  \caption{Descomposición SVD de la matriz A, y posterior recorte de los \emph{k} primeros elementos} 
\end{figure}

	Al momento de realizar una consulta, se genera un vector cuyo contenido consiste en 1's en las posiciones de las palabras buscadas, el cual opera de la siguiente forma con las matrices antes mencionadas:

  \begin{math}
  \\
  A = U*S*V^T 	\\
  q = q^T*U*S^{-1}	\\
  \end{math}

	Siendo \( q \) el vector consulta (o query), al cual luego se le calcula la ``similitud'', es decir, el ángulo que forma con la matriz de documentos V. Esto devolvera una serie de valores que corresponden al grado de relevancia de cada documento según la búsqueda realizada. Esta ``similitud'' se calcula a través de \emph{cosine similarity} calculado como:

\vspace{5 mm}

\( Similarity = cos( \theta ) = \frac{A \cdot B}{ ||A|| \cdot ||B|| } \)

\vspace{5 mm}

	Es posible graficar los documentos y los términos de una consulta en un mismo plano cartesiano, tal como se ve en la figura \ref{fig:grafico}, para poder determinar en forma gráfica la cercanía de los resultados con la consulta.

\begin{figure} 
  \centering 
    \includegraphics[width=10cm]{Imagenes/Consulta.png} 
  \caption{Representación gráfica de una consulta, junto con un set de documentos} 
  \label{fig:grafico}
\end{figure}\newpage

\section{Datos experimentales}
	\subsection{Tamaño de la matriz formada}

	Como base de datos para las pruebas preliminares se utilizó una cantidad parcial de artículos de Wikipedia, debido a la diversidad de tópicos y vocabulario que en la misma se puede encontrar, facilitando así la determinación de documentos relevantes ante una consulta.  

	El formato de almacenamiento utilizado para la matriz es el de Octave para matrices dispersas. Estos archivos tienen como encabezado la cantidad de filas, columnas y valores distintos a 0. Se prefirió el uso de matrices dispersas (las cuales guardan sólo los valores que son distintos de 0) en vez de matrices densas, ya que la cantidad de valores distintos a 0 es menor al 1 \% en la mayoría de los casos.

	En el siguiente cuadro se mostrarán el tamaño total de artículos tomados y su respectivo tamaño en la matriz final, dando como datos suplementarios pero no menos importantes la cantidad de términos extraídos (cabe aclarar que para esta etapa se consideró como término toda palabra separada por un espacio, y no se realizó ningún tipo de filtrado como puede ser el uso de funciones de ponderación de términos).

\vspace{6 mm}

\begin{tabular}{| c | c | c | c |}
  \hline                        
  Tamaño base de datos [\(Mb\)] & Tamaño matriz  [\(Mb\)]  & Documentos & Términos \\
\hline
  2 & 1.3 & 153 & 32.820\\
  5 & 3.4 & 361 & 57.383\\
  8 & 5.5 & 549 & 77.539\\
  12.1 & 8.1 & 781 & 98.828\\
  20 & 13.8 & 1209 & 135.159\\
  25.1 & 17.6 & 1469 & 155.555\\
  \hline  
\end{tabular}\newpage


\section {Diseño de la solución}

      El Trabajo Práctico se diagramó inicialmente 2 etapas, de las cuales sobresalen un total de 5 bloques principales, interrelacionados entre sí. \\
      Dichas etapas fueron:

  \begin{itemize}
  \item{\textbf{Indexación de archivos}}

	\subitem{Parseo de datos}
	\subitem{Determinación de contextos (Armado primario de términos)}
	\subitem{Determinación de términos propiamente dicha}
	\subitem{Armado y reducción de matriz}

  \item{\textbf{Realización de consultas}}
	\subitem{Devolución de búsquedas}
  \end{itemize}


	\subsection{Indexación}
    
	\subsubsection{Parseo de datos}
	Dado un universo de N documentos, el parser del programa es el encargado de recorrer cada uno de ellos extrayendo las palabras de a una, tomando como caracteres válidos solamente los de tipo alfanumérico, y algunos símboles especiales, como lo es el guión (-) ya que es frecuentemente utilizado para formar palabras compuestas.

	Cada palabra que es leída por el parser es empaquetada junto con su contexto, el cual es la palabra anterior en el texto (cabe destacar que la primera palabra del documento no posee contexto), y ambas son enviadas al generador de contextos del programa, que es el encargado de decidir fehacientemente cuales de las palabras compuestas serán consideradas como un término.

	
	\subsubsection{Determinación de Contextos}
	Esta etapa es la encargada de determinar la presencia en los textos de términos compuestos por 2 palabras, con la posibilidad de escalarlo a 3 o más.

	Las palabras van apareciendo en determinados contextos, los cuales son la palabra predecesora, y se van guardando por orden de aparición. Cada vez que una palabra se repite, se guarda un nuevo contexto de la misma si es que aún no existía, y en caso contrario, se incrementa el contador de apariciones del mismo.
	Cuando la ocurrencia de una palabra con un mismo contexto se repite una mayor cantidad de veces que un valor de tolerancia (determinado por la cantidad total de términos en el documento) el conjunto contexto-palabra pasa a ser un aspirante a término compuesto, ya que sólo con el número de ocurrencias en el documento no basta para determinar si 
	realmente puede considerarse como un término.\\


	Se define una función \( \delta[N] \) de modo tal de poder definir la constante que deberá superar la frecuencia de una determinada palabra en un contexto para el par “palabra-contexto” pase a ser considerado un término de orden 2. Luego de proponer distintas alternativas, se decidió que la función sólo dependería de la cantidad de palabras en ese contexto y se la definió de la siguiente manera:

\vspace{3 mm}
\( \delta[N] = MAX[ 6 , Trunc(0,3*N) ] \) , siendo N la cantidad de palabras en un contexto.
\vspace{3 mm}

	Es decir de este modo el valor más pequeño que toma la función es 6 apariciones en un contexto para ser considerado de orden 2, lo cual sucede para contextos de tamaño reducido (hasta 23 apariciones).  Luego si el contexto posee 24 o más  apariciones, la función toma por valor el 30\(\%\) de la cantidad de palabras en ese contexto creciendo de este modo de manera lineal y escalable con el tamaño de los contextos como bien se puede ver en la figura \ref{CrecimientoDelta}.

\begin{figure} [h]
  \centering 
    \includegraphics[width=13cm]{Imagenes/CrecimientoDelta.png} 
  \caption{ Crecimiento del delta } 
\label{CrecimientoDelta}
\end{figure}

	
	\subsubsection{Selección de términos}
	Una vez determinados todos los conjuntos de palabras compuestas que pueden ser un término, se aplica a los candidatos una función de selección de términos, denominadas en inglés como \emph{Term Selection functions}, la cual indica, según un valor numérico, el peso o la importancia que dicho término representa en el universo de documentos.

	Para la resolución de este trabajo práctico se eligió la discriminación de términos mediante el método de \emph{Ganancia de Información} (IG, del inglés Information Gain).

	El método consiste en la ponderación de los términos según el valor dado por la variación de la entropía media en los documentos cuando el término está presente, y cuando está ausente. Los resultados experimentales obtenidos al utilizar este método demuestran que en universos medianos de documentos, las mejoras en precisión y recall llegan hasta un 27\% y 26,5\% respectivamente, en comparación con los resultados obtenidos en un proceso de LSI base, es decir, sin ponderación de términos[\ref{Wu_Chou}].

	Uno de los motivos de la elección de este método de selección de términos, es debido a su capacidad de quitar algunas dependencias críticas del idioma en el cual se encuentran los textos, lo que hace al proyecto más robusto y mantiene el nivel de portabilidad entre idiomas que LSI tiene por defecto[\ref{Wu_Chou}].\newline

	El valor que da este método a cada término está dado por la siguente función:\newline

	\(IG(t_{i}) = H(C) - H(C|t_{i}) - H(C|t^{*}_{i}) \)\newline

	Donde:\newline

	\(H(C)) = - \sum_{i=1}^{n} p(c_{i}) log(p(c_{i})) \)\newline

	\(H(C|t_{i})) = -p(t_{i}) \Big[ \sum_{j=1}^{n}  p(c_{j}|t_{i})  log(p(c_{j}|t_{i})) \Big] \)\newline

	\(H(C|t^{*}_{i})) = -p(t^{*}_{i}) \Big[ \sum_{j=1}^{n}  p(c_{j}|t^{*}_{i})  log(p(c_{j}|t^{*}_{i})) \Big] \)\newline

	Siendo:\newline

	\(H(C))\): La entropía de las categorías

	\(H(C|t^{*}_{i})) \): La entropía condicional de las categorías cuando el término \(t_{i}\) está ausente

	\(H(C|t_{i})) \): La entropía condicional de las categorías cuando el término \(t_{i}\) está presente

	\(p(c_{i})\): La probabilidad de la categoría \(c_{i}\)

	\(p(c_{j}|t_{i})\): La probabilidad de la categoría \(c_{i}\) dado \(t_{i}\)

	\(p(c_{j}|t^{*}_{i})\): La probabilidad de la categoría \(c_{i}\) sin \(t_{i}\)\newline

	Una vez obtenidos los valores para todos los términos, estos son ordenados en forma descendente, y se seleccionan los que representen el 80\% del área bajo la curva de la distribución IG[\ref{Wu_Chou}].

	Luego de esto, se construye la matriz Términos-Documentos con los términos seleccionados.

	\subsubsection{Armado y reducción de la matriz - Ponderación de términos}

Se eligió el método del Sort externo para la construcción de la matriz inicial. El mismo consiste en levantar en memoria \(n\) elementos del archivo original, ordenarlos mediante algún metodo de tipo sort alfabéticamente y por documento (se realiza sort interno). Luego con las M particiones formadas se realiza un merge para finalmente obtener la matriz final.

Para hacer la división en valores singulares se realizó dicha parte en Octave por tener muchas optimizaciones relacionadas con el manejo de matrices. Desde el programa principal se invoca una función de Octave que carga la matriz generada luego de la lectura del archivo, se realiza el SVD, se recorta la matriz según un parámetro recibido y se vuelven a guardar en disco.

Finalmente, a cada elemento de la matriz se le aplicó una función de valoración (llamadas funciones de Term Weighting en inglés), conocida como Log*Entropía. Estas funciones tranforman el valor existente en la matriz M[i,j], que originalmente guarda la cantidad de apariciones del término \(i\) en el documento \(j\) en un producto entre una valoración local del término, y una global, con la intención de estimar la importancia del término en los documentos que aparece[\ref{Log*Entropy_1}].

Se seleccionó este método para la valoración de los términos debido a que en la práctica, se ha demostrado empíricamente que Log*Entropía sigue funcionando bien incluso con universos de documentos extensos[\ref{Log*Entropy_2}][\ref{Log*Entropy_3}][\ref{Log*Entropy_4}]. 

El método de Log*Entropía se basa en el producto de funciones que determinan el peso local y global de un término en un contexto dado. Para la determinación del peso local, se utiliza el logaritmo de la frecuencia del término en el documento, y en el peso global se tiene en cuenta la normalización de la entropía del término a lo largo del conjunto de documentos[\ref{Log*Entropy_1}][\ref{Log*Entropy_2}].

	La fórmula principal para el cálculo de Log*Entropía es la siguiente:\\

	\(Log*Entropia = log(tf_{i,j} + 1) * \Big[ 1+\sum_{j=1}^{N} \frac{p_{i,j}log(p_{i,j})}{log(N)} \Big] \)\\

	Donde:\\

	\(tf_{i,j}\): Es la frecuencia del término \(i\) en el documento \(j\)

	\(N\): Es la cantidad de documentos en la colección

	\(p_{i,j}\): Es el cociente entre \(tf_{i,j}\) y \(gf_{i}\), siendo \(gf_{i}\) la cantidad total de  veces que el término \(i\) ocurre en la colección de documentos


	\subsection{Búsquedas}
	Para hacer las consultas, primero se carga en memoria la lista de palabras en forma de vector para luego realizar búsqueda binaria sobre el mismo. Luego de obtener las coordenadas de cada palabra de la consulta se guarda el vector \emph{query} en memoria. Se ejecuta un codigo de octave que carga las 3 matrices que se obtuvieron del SVD y el vector \emph{query}, realiza la multiplicación correspondiente y guarda el vector de relevancias resultate en disco. Este último vector se carga desde el programa en un heap mientras se le hace un apareo con la lista de nombres de documentos. La lista de documentos final se obtiene desencolando los elementos del heap, tantos como se quieran mostrar.

Este proceso dura entre 2 o 3 segundos para una matriz de 100.000 elementos ya que la matriz descompuesta se guarda en formato de octave que es eficiente tanto en espacio como en velocidad de carga, y el vector de consulta se guarda como una matriz esparcida y al tener solo un elemento por termino de consulta este vector no puede ocupar más de 10 \( kb \).

	 Para armar el vector \emph{query}, los términos utilizados en la consulta también son pasados por una función de Term Weighting, pero sólo se considera la función que determina el peso global del término en el universo de documentos. Para hacer esto, se pueden tomar los valores existentes en la fila que representa al término de la consulta (los cuales representan los valores devueltos por el método de Log*Entropía), realizar la sumatoria y tomar como referencia el valor más alto conseguido con los términos de la query. Ese término tendrá un 1 en dicho vector, y los demás un valor entre 0 y 1 que represente la fracción correspondiente.

	De esta manera, se realiza una ponderación a los términos de la consulta, obteniendo resultados más cercanos al esperado\newpage
	

\section {Análisis de la solución y la implementación}
	
		
	\subsection{Mejoras a través del uso de redes neuronales}
	
	Comúnmente tenemos contacto con algoritmos de búsqueda de información relevante en aplicaciones como buscadores online, donde podría ser un importante ejemplo Google. Al permitir que se realizen muchas búsquedas con esta aplicación, estamos contando con una información importante que puede mejorar la eficiencia del algoritmo. 
Comunmente al mostrar los resultados de una búsqueda se muestra el título del artículo o página junto con un extracto de esta, luego es el usuario el que elije, entre los artículos o páginas disponibles, cuál es el más acertado basándose primero en estos extractos. Estos aportes que hacen los usuarios simplemente eligiendo una de las opciones mostradas según el criterio de su búsqueda puede ser fácilmente aprovechable a través de una red neuronal.

Esta red neuronal tendría como entradas la búsqueda del usuario, es decir en la capa cero habría \( n \) nodos, siendo \( n \) la cantidad de palabras indexadas. La cantidad de capas intermedias tendería en un principio a ser la misma cantidad de nodos de salida por cuestiones de eficacia, pero podría reducirse para que el tiempo de entrenamiento y de predicción no sea exagerado. Para la última capa, la de salida, habría tantos nodos como documentos ya que buscamos que esta red neuronal enliste, a partir de la entrada del usuario, la relevancia de cada articulo. Para esto último es conveniente usar una funcion logística ya que devolvería un valor entre 0 y 1 para cada documento, según su relevancia.

La tabla de datos para el entrenamiento de la red neuronal estaría formada por las entradas del usuario, y como respuesta buscada se podrían usar las estadisticas de qué artículo fue el más elegido.

\vspace{5 mm}

\begin{tabular}{| c | c | c | c || c |}
  \hline                        
  a & after & and & ... & Documento	\\
\hline
  1 & 0 & 0 & ... & 105 \\
  0 & 1 & 1 & ... & 502 \\
  \hline  
\end{tabular}

\vspace{5 mm}

La función de costo que se usará va a ser la típica de regresión logística:

\( \\ J(\theta) = -\frac{1}{m} \Big[ \sum_{i=1}^{m}  y^{(i)} log h_{ \theta } (x^{(i)}) + (1 - y^{(i)}) log(1 - h_{ \theta }(x^{(i)}) ) \Big] + \frac{ \lambda }{2m} \sum_{j = 1}^{n} \theta^{2}_{j} \\ \)

Donde tenemos que \( m \) es la cantidad total de casos de entrenamiento, \( \lambda \) el término de regularización y la función \( h_{ \theta } \) está definida como \( \frac{1}{1 + e^{- \theta^{T}x }} \) para obtener siempre valores entre 0 y 1 por la razon antes mencionada. Siendo \( \theta \) la variable a ajustar.

Luego de tener esta red nueronal contariamos con la prediccion de relevancia de documentos hecha por el LSI y por esta red. Para que las relevancias finales cuenten con un cierto porcentaje de cada metodo se podria hacer una combinación de ambos de la forma.

\( \\ relevancia\_documento = \alpha * (relevancia\_por\_LSI) + (1- \alpha)*(relevancia\_ red\_neuronal) \\ \)

A través de la variacion de \( \alpha \) tendriamos que cada metodo afecta de una forma menos o más significativa a los resultados, esta constante se estableceria a traves de la experimentacion y dependeria en gran parte de los casos de entrenamiento con los que cuente la red neuronal.

	
	\subsection{Term Weighting y Term Selection}

	Como se mencionó anteriormente, es un proceso importante en LSI la ponderación de los términos existentes, tanto para la elección de los que finalmente formarán parte de la matriz M, como para determinar el valor que existirá en la posición M[i,j], donde \emph{i} corresponde al i-ésimo término de la matriz, y \emph{j} al j-ésimo documento, por lo que en dicha posición quedará el valor determinante de la importancia o peso del término en el documento.

	Existen gran cantidad de métodos para los conocidos ``Term Weighting`` y ``Term Selection``, y finalmente se optó por el de Log*Entropía para el primero, y Ganancia de Información (IG) para el segundo, por motivos ya expuestos. A continuación se enumerarán otros métodos estudiados y tenidos en consideración durante la elección final, y se dará una breve reseña de cada uno.

	\subsubsection{Pointwise Mutual Information}

	El método de Información Mutua Puntual (MI), mide básicamente la probabilidad de que dos eventos se produzcan simultáneamente en comparación con la probabilidad de que ocurra cada uno de manera independiente[\ref{MI_1}]. Se trata de un método sencillo, que también puede utilizarse para la determinación de palabras múltiples, tomando en cuenta los contextos en los que aparecen[\ref{MI_2}][\ref{MI_3}].

	La fórmula principal para el cálculo de MI es la siguiente:\\

	\(MI(C,t)=log_{2} \frac{P(C,t)}{P(C)P(t)}\)\\

	Donde:\\

	\(C\): Refiere al documento C

	\(t\): Refiere al término t

	\(P(C,t)\): Es la probabilidad conjunta del término t en el documento C

	\(P(C)\): Es la probabilidad de aparición del documento C

	\(P(t)\): Es la probabilidad de aparición del término t


	\subsubsection{Odds Ratio}

	El método de Relación de Probabilidades (OR) está basado en la idea de que la distribución de los conceptos es distinta en los documentos relevantes respecto de los que no lo son, por lo que emplea un cociente de probabilidades condicionales[\ref{Zhaohui}].

	La fórmula principal para el cálculo de OR es la siguiente:\\

	\(OR(t,C)= \frac{P(t|C)P(t^{*}|C^{*})}{P(t^{*}|C)P(t|C^{*})} \)\\

	Donde:\\

	\(P(t|C)\): Es la probabilidad condicional del término t, dado el documento C

	\(C^{*}\): Refiere a la ausencia del documento C

	\(t^{*}\): Refiere a la ausencia del término t

	\subsubsection{Tf*IDF}

	El método de Tf*IDF, al igual que el de Log*Entropía, se basa en el producto de funciones de peso local y global del término en un contexto dado. En este caso, para la determinación del peso local, se utiliza la frecuencia del término en el documento, y en el peso global se tiene en cuenta la frecuencia inversa de los documentos[\ref{Log*Entropy_1}][\ref{Log*Entropy_2}].

	La fórmula principal para el cálculo de Tf*IDF es la siguiente:\\

	\(Tf*IDF = tf_{i,j}  *  log_{2} \Big( \frac{N}{df_{i}} \Big) \)\\

	Donde:\\

	\(tf_{i,j}\): Es la frecuencia del término \(i\) en el documento \(j\)

	\(N\): Es la cantidad de documentos en la colección

	\(df_{i}\): Es la cantidad de documentos donde el término \(i\) aparece

	\subsubsection{Chi-Cuadrado}

	El método \(\chi^{2}\) mide la falta de independencia entre un término y una categoría, y se puede comparar con la distribución chi-cuadrado de un grado de libertad[\ref{Zhaohui}][\ref{Chi_Square1}].

	La fórmula principal (en una de sus tnatas formas) para el cálculo de \(\chi^{2}\) es la siguiente[\ref{Chi_Square2}]:\\

	\(\chi^{2}(t_{k},C_{i}) = \frac{[P(t_{k},C_{i}) P(t^{*}_{k},C^{*}_{i}) - P(t^{*}_{k},C_{i}) P(t_{k},C^{*}_{i})]^{2} } { P(t_{k} P(t^{*}_{k} P(C_{i}) P(C^{*}_{i}) }\)\\

	Donde:\\

	\(P(t_{k},C_{i})\): Es la probabilidad conjunta del término \(t_{k}\) en el documento \(C_{i}\)

	\(t^{*}_{k}\): Refiere a la ausencia del término \(t_{k}\)

	\(C^{*}_{i}\): Refiere a la ausencia del documento \(C_{i}\)

	\subsubsection{Coeficiente GSS}

	El coeficiente GSS es una simplificación del método \(\chi^{2}\), donde la importancia de los términos asciende junto con el valor de la ponderación, por lo que solamente se consideran los ponderados positivos[\ref{Zhaohui}].

	La fórmula principal para el cálculo de GSS es la siguiente:\\

	\(GSS(C,t)=P(C,t)P(C^{*},t^{*}) - P(C^{*},t)P(C,t^{*})\)\\

	Donde:\\

	\(P(C,t)\): Es la probabilidad conjunta del término t en el documento C

	\(C^{*}\): Refiere a la ausencia del documento C

	\(t^{*}\): Refiere a la ausencia del término t

	\subsubsection{Coeficiente NGL}

	El coeficiente NGL, tambien conocido como Coeficiente de Correlación (CC) es otra simplificación del método \(\chi^{2}\), utilizando en su definición el valor del coeficiente GSS[\ref{Zhaohui}]. Puede notarse que \(GSS^{2} = \chi^{2} \). En este método nuevamente la importancia de los términos asciende junto con el valor de la ponderación, por lo que solamente se consideran los ponderados positivos, y mientras mayor es el valor, más relevancia se le da al término.

	La fórmula principal para el cálculo de NGL es la siguiente:\\

	\(NGL(C_{i},t_{k})= \frac{\sqrt{N} GSS(C_{i},t_{k})}{ \sqrt{P(t_{k} P(t^{*}_{k} P(C_{i}) P(C^{*}_{i})} }\)

	Donde:\\

	\(N\): Es la cantidad total de documentos en la colección
 
	\(C^{*}\): Refiere a la ausencia del documento C

	\(t^{*}\): Refiere a la ausencia del término t


	\subsection{Términos}

	El primer problema que surge al diseñar la implementación del práctico es el de diferenciar que es un término y que no a la hora de parsear los documentos para armar la matriz principal.

  Para empezar, se deben eliminar los términos que son muy frecuentes y aparecen en repetidos documentos según una cierta tolerancia. Palabras de este estilo (como conectores logicos) no son consideradas terminos ya que son poco relevantes para identificar un contexto determinado.

  Otra consideración a tener en cuenta es el tamaño de los términos, los cuales pueden ser de n-términos (\( n \ge 1 \) ).
	En el caso más sencillo es el de los términos de orden simple o uno, es decir, cada palabra es un término relevante en el documento.
	Se considera un término de orden múltiple a aquellos términos compuestos por 2 o más palabras.


	\subsubsection{Búsqueda de la función de selección de términos multi-palabra}

	Se buscó una función \( \delta \) con la finalidad de establecer un la diferencia entre un termino de orden 1 y uno de orden 2 según la frecuencia de aparición de una palabra en un determinado contexto, sean:

	M: cantidad de palabras de un texto.

	N: cantidad de apariciones de un contexto.

	C: la cantidad de contextos diferentes en un texto.

	\vspace{5 mm}

	Se probaron distintas funciones en base a estos parámetros. La primera y más intuitiva resulto ser:\\

\( \delta(M,N)= Trunc[M/N] \)\\

Pero una función de esta índole no resulto ser adecuada, puesto que al ser M constante para un texto, si N es grande ( \( \sim \)M)  el  \( \delta \) se hace muy pequeño entonces casi todos serian considerados términos de orden 2. Ahora  bien caso contrario N muy pequeño (\( \sim \)1) el  \( \delta \) es muy grande, con lo que casi ningún termino seria considerado de orden 2.

\vspace{5 mm}
Motivados por este inconveniente se planteó:\\

\( \delta(M,N) = Trunc[ \frac{M}{M-N}\) ]\\

Que si bien aparento solucionar dicho inconveniente traía aparejado otro inconveniente ya que F toma el valor 1 para todo N perteneciente al intervalo (1,Z) siendo \( Z= M –  \epsilon \) es decir  \( \delta \) cambiaba muy bruscamente a partir de un  \( \epsilon \) tal que \( |M-  \epsilon | < \omega \) bastante pequeño.

\vspace{5 mm}

Luego, se intentó reescalar ambos miembros (cociente y denominador) de modo de hacerla más espaciada.
Se propusieron factores cuadráticos, logarítmicos, entre otros. Algunas funciones propuestas fueron:

\vspace{5 mm}

\( \delta[M,N] = [ \frac{N^2}{10(M-N)}]\)\\

\( \delta[M,N]= \Big[ \frac{N^2}{[((M-N)^1/2)(M-N)]} \Big]  \)

\vspace{5 mm}

También se intentaron plantear funciones del tipo \( \delta[M,N,C]  \) pero estas fórmulas funcionaban bien sólo en determinados casos, el crecimiento no era muy uniforme y eran difíciles de probar para cualquier valor.

Decidimos entonces que un buen  \( \delta \) debía variar linealmente con la escala de nuestro problema.

Se propuso algo de la forma \( \delta = aX+b \) que fue finalmente la opción seleccionada y se decidió que sólo debía depender de N.

	\subsubsection{Términos  de orden 2 }
	
  Un término de orden dos es un término compuesto por dos palabras. Algunos ejemplos de estos son “San Francisco” o  “Apple computers”.

  Para implementar esto, se crea un contexto de orden 1 por cada palabra que aparezca en el documento y se lleva la cuenta de la cantidad de veces que aparece dicha palabra en un contexto determinado.
  Ejemplo: si un texto menciona 20 veces  el termino “san francisco” entonces la palabra francisco aparecerá 20 veces en el contexto “san” cuando estas ocurrencias ocurren mas veces que una cierta tolerancia  entonces “san francisco” para a ser considerado un termino para introducir en la matriz.

  Asimismo, podría ocurrir que en mi documento aparezca además 4 veces la palabra “san” y la palabra “francisco”  3 veces en otro contexto, entonces los contextos quedarían:

  \begin{itemize}
  \item Contexto “san”:
  \begin{itemize}
  \item Terminos:
   \begin{itemize}
  \item “francisco”: 20 ocurrencias
  \item otras palabras: 4 ocurrencias
  \end{itemize}
  \end{itemize}
  \end{itemize}

  \begin{itemize}
  \item Contexto “francisco”:
  \begin{itemize}
  \item Terminos:
  \begin{itemize}
  \item cualquier palabra/s: 23 ocurrencias en palabras distintas. (ocurrencias menor que la tolerancia.)
  \end{itemize}
  \end{itemize}
  \end{itemize}

  Entonces si la tolerancia es \( \ge 10 \) ocurrencias por contexto:

  \begin{itemize}
  \item el termino “san francisco” tendrá una ocurrencia de 20 apariciones
  \item el termino “san” tendrá una ocurrencia de 4 ocurrencias ( \(\sharp\) ocurrencias(“San”)= \(\sharp\) ocurrencias(“CtxSan”)-  \(\sharp\) ocurrencias(“FranciscoEnCtxSan”))
  \item el termino “francisco” tendrá una ocurrencia de 3 ocurrencias ( \(\sharp\) ocurrencias(“francisco”) =  \(\sharp\) ocurrencias(“CtxFrancisco”) -( \(\sharp\) ocurrencias(“FranciscoEnCtxSan”))
  \end{itemize}

  \subsubsection{Términos  de orden 3 y superiores}
  
  Un término de orden tres es un término compuesto por tres palabras. Algunos ejemplos de estos podrían ser “San Francisco bridge” o  “Apple personal computers”.

  Se evalúa la posibilidad como opcional de tener en cuenta estos términos de órdenes superiores con una implementación similiar a los términos de orden 2 pero utilizando contextos más amplios.

  Esta implementación generaría una mejora en las búsquedas, pero implicaría un proceso de los textos mucho más grande, ya que se toman más palabras como contexto, y eleva la cantidad de combinaciones en un factor realmente importante, por lo que sólo sería factible su uso en colecciones pequeñas de documentos, o en casos en los que el tiempo de indexación y los recursos computacionales disponibles no sean un impedimento.

  \subsection{Consultas Interesantes}
 
A través del uso de los contextos dentro del proyecto, se intenta encontrar y formar términos compuestos que den resultados más precisos. Hay casos de términos tales como ``science fiction``, nombres de personas o lugares, compuestos químicos como ``hydrochloric acid``, y una gran cantidad de ejemplos más, que a pesar de estar formados por palabras que pueden aparecer separadas, al hacer una búsqueda por el término entero, se obtienen resultados mucho mejores.

Con estas técnicas de discriminación de términos compuestos hay que tener cuidado a cierto conjunto de palabras que muchas veces aparecen seguidas, como puede ser ``is the`` o ``it is``.

Decidimos dejar los caracteres numéricos ya que en muchos casos tienen significancia, como pueden ser fechas, años o, incluso, nombres de estándares como ``ISO 9001`` que también pasaría a ser un término compuesto. Además de esto pueden ocurrir casos de números poco significativos para una búsqueda, como pueden ser estadísticas o cantidades de elementos.

Como es sabido, en las búsquedas siempre existen términos que tienen una mayor importancia que otros, por lo que es deseable que los resultados obtenidos tengan mayor cercanía a estos.
A través de los algoritmos de Term Weighting podemos obtener un numero que representa la cantidad de información que aporta una palabra al realizar una consulta, por ejemplo: ``The`` aporta mucha menos información que ``science``, siendo que la primera aparece en casi todos los documentos tratados, mientras que la segunda solo en aquellos que tengas alguna relación con la ciencia. Con este valor obtenido por una funcion de ponderación de términos en la consulta, podemos agregar al vector de búsqueda, en vez de solo unos, un valor entre 0 y 1 dependiendo de la información que aporta cada término, como ya fue explicado con anterioridad.\newpage

\section{Conclusiones}

A partir de este práctico pudimos observar, relacionar y aplicar a partir de la investigación, conceptos ya incorporados en otras asignatura así como también otros desconocidos.

A través de LSI aprendimos como se pueden realizar búsquedas muy precisas solucionando el problema de la sinonimia que presentaban otros métodos y como construir conceptos a partir de contextos similares en un documento. Si bien este método es poderoso es posible agregar variaciones, como las que se adjuntan en este trabajo, para mejorar la eficacia de las búsquedas. Como desventajas, y a pesar de ser escalable, se encuentra el gran tamaño y tiempo de calculo que puede llevar la descomposición en valores singulares, que en muchos casos, sin una base de datos demasiado grande, se puede llegar a ocupar más de los 2 GB de memoria que normalmente tiene una computadora, se suman a estas ultimas el tamaño de las matrices factorizadas.

Como esta matriz se arma tan solo una única vez y al tratarse tan solo de una multiplicación vectorial y un simple calculo de similitud de vectores para obtener el vector resultado, es que las querys resultan bastante ágiles. Por estos motivos este algoritmo, así como fue presentado e implementado, se muestra muy práctico y rápido para bases de datos menores a 1Gb, con generación del repositorio en un tiempo mediano y búsquedas rápidas. Para bases de datos más grandes los tiempos de generación del repositorio se vuelven mucho mayores, implicando además un gran consumo de recursos en la computadora, haciéndolo en la mayoría de los casos impracticable para sistemas de indexación de 32bits, ya que no es posible mapear en memoria la cantidad de datos usads al mismo tiempo.

Finalmente, se puede remarcar que se investigaron y se compararon distintos métodos para cada sección del practico, pudiendo así entender las ventajas y desventajas de cada uno en su aplicación con LSI.\newpage

\section{Referencias}

  \begin{enumerate}
  \item Furnas, G.W., Landauer, T.K., Gomez, L.M., and Dumais, S.T. Statistical semantics:
  Analysis of the potential performance of key-word information systems. Bell System
  Technical Journal, 1983, 62(6), 1753-1806.	\label{FurnasLandauer}

  \item Wikipedia. Article: Sinonimia \label{Sinonimia}

  \item Wikipedia. Article: Polisemia \label{Polisemia}

  \item Scott Deerwester. Indexing by Latent Semantic Analysis. \label{Scott_Deerwester}

  \item Thomas K Landauer. An Introduction to Latent Semantic Analysis.  \label{Thomas_Landauer}

  \item Li Li, Wu Chou. Improving Latent Semantic Indexing based classifier with Information Gain. \label{Wu_Chou}

  \item Bárbara Rosario. Latent Semantic Indexing: An overview. \label{Barbara_Rosario}

  \item Gabriel Recchia and Michael Jones. More data trumps smarter algorithms:
  Comparing pointwise mutual information with latent semantic analysis -
  Behavior Research Methods 2009, 41 (3), 647-656 \label{MI_1}

  \item Wikipedia. Article: Pointwise Mutual Information. \label{MI_2}

  \item Pointwise Mutual Information.
  URL: http://www.eecis.udel.edu/\(\sim\)trnka/CISC889-11S/ lectures/philip-pmi.pdf \label{MI_3}

  \item Zhaohui Zheng, Rohini Srihari. Optimally Combining Positive and Negative Features 
  for Text Categorization\label{Zhaohui}

  \item Guillermo Jorge-Botana, Jose Leon, Ricardo Olmos and Inmaculada Escudero
  Latent Semantic Analysis Parameters for Essay Evaluation using Small-Scale Corpora\label{Log*Entropy_1}

  \item Wikipedia. Article: Latent Semantic Indexing. \label{Log*Entropy_2}

  \item Landauer, T., et al., Handbook of Latent Semantic Analysis, Lawrence Erlbaum Associates, 2007. \label{Log*Entropy_3}

  \item Man Lan, ChewLin Tan, SAmYuan Sung, HweeBoon Low. A comprehensive Comparative Study on
  Term Weighting Schemes for Text Categorization \label{Log*Entropy_4}

  \item Kotaro Hashimoto and Takashi Yukawa - Nagaoka University of Technology
  Term Weighting Classification System Using the Chi-square Statistic for the 
  Classification Subtask at NTCIR-6 Patent Retrieval Task \label{Chi_Square1}

  \item Franca Debole and Fabrizio Sebastiani - Istituto di Scienza e Tecnologie dell’Informazione
  Consiglio Nazionale delle Ricerche Via Giuseppe Moruzzi
    Supervised Term Weighting for Automated Text Categorization \label{Chi_Square2}

  \end{enumerate}
\end{document}
